#define _CRT_SECURE_NO_WARNINGS

#include"Binary.h"


struct TreeNode {
    int val;
    struct TreeNode* left;
   struct TreeNode* right;
};


struct TreeNode* sb5(int x)
{
    struct TreeNode* tmp = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    if (tmp == NULL)
        exit(-1);
    tmp->val = x;
    tmp->left = NULL;
    tmp->right = NULL;
}



int nmax(struct TreeNode* root)
{
    if (root == NULL)
        return 0;
    return nmax(root->left) + nmax(root->right) + 1;
}
void _distanceK(struct TreeNode* root, struct TreeNode* target, struct TreeNode* p, int k, int* i, int* tmp, int l, int* flag)
{
    if (root == NULL)
        return;
    if (root == target)
    {
        if (k == 0)
        {
            tmp[(*i)++] = root->val;
            return;
        }
        _distanceK(root->left, target, root, k, i, tmp, l + 1, flag);
        _distanceK(root->right, target, root, k, i, tmp, l + 1, flag);
        if (p && root == p->left)
            *flag = 1;
        else if (p && root == p->right)
            *flag = 2;
        return;
    }
    if (l || *flag)
    {
        if (k == l)
        {
            tmp[(*i)++] = root->val;
            return;
        }
        _distanceK(root->left, target, root, k, i, tmp, l + 1, flag);
        _distanceK(root->right, target, root, k, i, tmp, l + 1, flag);
        return;
    }
    _distanceK(root->left, target, root, k, i, tmp, l, flag);
    if (*flag == 1)
    {
        *flag = 0;
        l = 2;
    }
    if (*flag == 1 && k == 1)
    {
        tmp[(*i)++] = root->val;
        *flag = 0;
        return;
    }
    _distanceK(root->right, target, root, k, i, tmp, l, flag);
    if (*flag == 2 && k == 1)
    {
        tmp[*(i)++] = root->val;
        *flag = 0;
        return;
    }
    if (*flag == 2)
    {
        *flag = 0;
        _distanceK(root->left, target, root, k, i, tmp, 2, flag);
    }
}

int* distanceK(struct TreeNode* root, struct TreeNode* target, int k, int* returnSize)
{
    int n = nmax(root);
    int* tmp = (int*)malloc(sizeof(int) * n);
    *returnSize = 0;
    int flag = 0;
    _distanceK(root, target, NULL, k, returnSize, tmp, 0, &flag);
    return tmp;
}


int main()
{
	char a[] = { "ABD##E##CF##G##" };
	int n = strlen(a);
	int pi = 0;


	BTNode*tmp=BinaryTreeCreate(a, n, &pi);
    
    struct TreeNode* n1 = sb5(0);
    struct TreeNode* n2 = sb5(1);
    struct TreeNode* n3 = sb5(3);
    struct TreeNode* n4 = sb5(2);
    struct TreeNode* n5 = sb5(5);
    struct TreeNode* n6 = sb5(1);
    struct TreeNode* n7 = sb5(1);
    struct TreeNode* n8 = sb5(2);
    struct TreeNode* n9 = sb5(1);
    struct TreeNode* n10 = sb5(0);
    struct TreeNode* n11= sb5(8);
    struct TreeNode* n12 = sb5(8);

    n1->left = n2;
    n2->left = n3;
    n2->right = n4;
    
    int size = 0;
    distanceK(n1, n4, 1, &size);
    

	BinaryTreeLevelOrder(tmp);
	printf("\n");
	
	int xz=BinaryTreeComplete(tmp);

	printf("%d\n",BinaryTreeSize(tmp));

    printf("%d\n", BinaryTreeLeafSize(tmp));
	printf("%d\n", BinaryTreeLevelKSize(tmp,3));
	BTNode* cur=BinaryTreeFind(tmp, 'F');
	printf("%c\n", cur->data);

	BinaryTreeDestory(&tmp);

	return 0;
}